#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

/*
 * line : 原数列
 * l, r, d, : 题目要求的 对于每个区间的左端点 右端点 值
 * change : 差分数组
 * 题解：对采用的订单数进行二分，每次用差分数组优化处理当天需要的教室数并与当天可对外借出的教室数比较检验。
 */

int line[1000010], l[1000010], r[1000010], d[1000010], change[1000010], diff[1000010];
int n, m;

bool check(int x)
{
    memset(change, 0, sizeof(change));
    memcpy(change,diff,4*(n+1));


    for (int i = 1; i <= x; i++) 
    {
        change[l[i]] -= d[i];
        change[r[i] + 1] += d[i];
        //用差分数组对前x个操作进行处理 记录区间操作
    }


    for (int i = 1; i <= n; i++)
        change[i] = change[i - 1] + change[i];
    //抹平差分数组

    

    for (int i = 1; i <= n; i++)
        if (change[i] < 0)
            return false;
    //出现借不出的情况

    return true;
}

int main()
{
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &line[i]);
        diff[i] = line[i] - line[i - 1];
      
    }

    for (int i = 1; i <= m; i++)
        scanf("%d %d %d", &d[i], &l[i], &r[i]);

    if (check(m)) // obj 4什么情况是全都可以成立
    {

        printf("0");
    }
    else
    {
        int left = 1, right = m, mid;
        while (left <= right)
        {
            mid = (left + right) >> 1;
            if (check(mid))
                left = mid + 1;
            else
                right = mid - 1;
        }
        printf("-1\n");
        printf("%d", left);
    }

    //system("pause");

    return 0;
}